|
In the mathematical field of graph theory, the Tutte 12-cage or Benson graph〔 is a 3-regular graph with 126 vertices and 189 edges named after W. T. Tutte. The Tutte 12-cage is the unique (3-12)-cage . It was discovered by C. T. Benson in 1966.〔Benson, C. T. "Minimal Regular Graphs of Girth 8 and 12." Canad. J. Math. 18, 1091–1094, 1966.〕 It has chromatic number 2 (bipartite), chromatic index 3, girth 12 (as a 12-cage) and diameter 6. Its crossing number is 170 and has been conjectured to be the smallest cubic graph with this crossing number.〔Exoo, G. ("Rectilinear Drawings of Famous Graphs" ).〕〔Pegg, E. T. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009.〕 ==Construction== The Tutte 12-cage is a cubic Hamiltonian graph and can be defined by the LCF notation (27, –13, –59, –35, 35, –11, 13, –53, 53, –27, 21, 57, 11, –21, –57, 59, –17 )7.〔Polster, B. A Geometrical Picture Book. New York: Springer, p. 179, 1998.〕 There are, up to isomorphism, precisely two generalized hexagons of order ''(2,2)'' as proved by Cohen and Tits. They are the split Cayley hexagon ''H(2)'' and its point-line dual. Clearly both of them have the same incidence graph, which is in fact isomorphic to the Tutte 12-cage.〔 The Balaban 11-cage can be constructed by excision from the Tutte 12-cage by removing a small subtree and suppressing the resulting vertices of degree two.〔Balaban, A. T. "Trivalent Graphs of Girth Nine and Eleven and Relationships Among the Cages." Rev. Roumaine Math 18, 1033–1043, 1973.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Tutte 12-cage」の詳細全文を読む スポンサード リンク
|